<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <meta http-equiv="X-UA-Compatible" content="ie=edge" />
    <title>智能蛇 | Hugo Theme Dream</title>

    



<meta name="author" content="Lindixuan" />
<meta name="description" content="" />



<meta name="generator" content="Hugo 0.63.2" />

<link rel="canonical" href="https://lindixuan.gitee.io/%E6%99%BA%E8%83%BD%E8%9B%87/" />


<meta property="og:title" content="智能蛇" />
<meta property="og:description" content="" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://lindixuan.gitee.io/%E6%99%BA%E8%83%BD%E8%9B%87/" />
<meta property="article:published_time" content="2020-09-20T12:48:58+08:00" />
<meta property="article:modified_time" content="2020-09-20T12:48:58+08:00" />



<meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content="智能蛇"/>
<meta name="twitter:description" content=""/>


<link rel="stylesheet" href="/css/semantic.min.css" />
<link rel="stylesheet" href="/css/OverlayScrollbars.min.css" />
<link rel="stylesheet" href="/css/github-markdown.css" />
<link rel="stylesheet" href="/css/site.css" />


<style>
  a {
    color: seagreen !important;
  }
</style>



<style>
  .inverted a {
     color: darkseagreen !important;
  }
</style>


    


  
    <link rel="stylesheet" data-highlight href="https://cdn.jsdelivr.net/gh/highlightjs/cdn-release/build/styles/gruvbox-light.min.css" />
  



  </head>

  
  <body style="background: white;">
  
    
<nav class="ui secondary inverted menu dream-menu">

  <div class="item">
    <i class="large link bullseye icon dream-flip-toggle" title="Flip it!"></i>
  </div>
  <div class="item">
    <i class="large link home icon" title="Home" onclick="window.location.href = 'https:\/\/lindixuan.gitee.io'"></i>
  </div>
  <div class="item">
    <i class="large link icon theme-switch" onclick="themeSwitch()"></i>
  </div>
  
  <div class="item">
    <i class="large link search icon" onclick="toggleSearch()"></i>
  </div>
  
</nav>

    <div class="flip-container">
      <div class="flipper">
        <section class="front">
          <div class="dream-max-width">
            
<div class="ui centered relaxed grid dream-grid">
  <div class="sixteen wide mobile sixteen wide tablet twelve wide computer column markdown-body dream-single">

    <section class="ui top attached segment" id="dream-save-post-as-img">
      <header style="margin-top: 0 !important;">
        <h1 class="ui large header">
          智能蛇
          <div class="sub header">
            @
            
              Lindixuan
            
            · Sunday, Sep 20, 2020
            · 2 minute read
            · Update at Sep 20, 2020
          </div>
        </h1>
      </header>

      
        <img class="ui image" style="margin-top: 2rem;" src="" />
      

      <article style="margin-top: 2rem;"><h2 id="介绍">介绍</h2>
<blockquote>
<p>智能蛇的设计目标是，用算法控制蛇自动寻路，让蛇像人一样能预判下一步情况，向食物移动的同时又要保证自己不会因为撞墙或者撞到身体而死亡。所以，我们需要通过算法实现从感知到决策再到行动。<br>
具体的思路是，要保证蛇吃食物而不死，可以让蛇头尽量追着蛇尾走，因为蛇头蛇尾移动速度是一样的，所以不用担心撞上。<br>
要注意的问题有：</p>
<ol>
<li>蛇的身体以及地图的边界是不可接触的格子，相当于障碍物；</li>
<li>因为贪吃蛇移动是一个动态的过程，所以每走一步，要重新进行寻路；</li>
<li>吃完食物蛇的长度变长，蛇尾巴位置不变，因此食物跟尾巴之间要留有空隙；</li>
<li>如果一直跟着尾巴走，就永远不会没有路；</li>
<li>随机出现的食物位置可能会堵住蛇头部到尾巴的路径，使得头部没有办法找到尾巴，但只要食物与尾巴之间有空隙，吃掉食物是安全的，而且可以重新找到从头部到尾巴的路径。</li>
</ol>
</blockquote>
<blockquote>
<p>可以采用贪心算法来实现寻路，决策思想是走曼哈顿距离fabs(snakeX[0]-foody)+fabs(snakeY[0]-foodx)最小且不会死掉的方向。寻路函数为：</p>
</blockquote>
<pre><code>char whereGoNext() {
    char movable[4]= {'D','A','S','W'};
    int min=9999,minDir;
    for(int i=0; i&lt;4; i++) {
        snakeX[0]+=direx[i];
        snakeY[0]+=direy[i];

        if(!gameover()) {
            int cost=fabs(snakeX[0]-foody)+fabs(snakeY[0]-foodx);
            if(min&gt;cost) {
                min=cost;
                minDir=i;
            }
        }

        snakeX[0]-=direx[i];
        snakeY[0]-=direy[i];
    }
    if(min&lt;9999)
        return movable[minDir];
    else return 0;
}
</code></pre><h2 id="实现代码如下">实现代码如下</h2>
<pre><code> #include&lt;stdio.h&gt;
#include&lt;stdlib.h&gt;
#include&lt;math.h&gt;
#include&lt;time.h&gt;
#include&lt;unistd.h&gt;

#define SNAKE_MAX_LENGTH 150
#define SNAKE_HEAD 'H'
#define SNAKE_BODY 'X'
#define BLANK_CELL ' '
#define SNAKE_FOOD '$'
#define WALL_CELL '*'
#define MAP_LENGTH 12
#define DELAY_TIME  100000  //delay 100ms

//move snake
void snakeMove(int dir);
//output cells of the grid
void show(void);
//output snake
void output(void);
//put a food randomized on a blank cell,1 for put food successfully,0 for fail
int putFood(void);
//judge whether gameover;0 for not over,1 for game over
int gameover(void);
//decide the smart snake's direction
char whereGoNext(void);

char map[MAP_LENGTH][MAP_LENGTH+1]= {//initial status
    &quot;************&quot;,
    &quot;*XXXXH     *&quot;,
    &quot;*      *   *&quot;,
    &quot;*      *   *&quot;,
    &quot;*     **   *&quot;,
    &quot;*      *   *&quot;,
    &quot;*          *&quot;,
    &quot;*          *&quot;,
    &quot;*          *&quot;,
    &quot;*          *&quot;,
    &quot;*          *&quot;,
    &quot;************&quot;
};
const int direx[4]= {0,0,1,-1};
const int direy[4]= {1,-1,0,0};
int snakeX[SNAKE_MAX_LENGTH]= {5,4,3,2,1};
int snakeY[SNAKE_MAX_LENGTH]= {1,1,1,1,1};
int snakeLength=5;
int foodx,foody,eatFood=1;

int main(void) {
    char s;
    srand(time(NULL));
    printf(&quot;\033[2J&quot;);//clear the screen
    printf(&quot;\033[1;1H&quot;);
    show();
    do {
        s=whereGoNext();
        if(s==0)break;
        switch(s) {
            case 'D':
                snakeMove(0);
                break;
            case 'A':
                snakeMove(1);
                break;
            case 'S':
                snakeMove(2);
                break;
            case 'W':
                snakeMove(3);
                break;
        }
        output();
        usleep(DELAY_TIME);
    } while(!gameover());
    printf(&quot;\033[13;1HGame over!!!\n&quot;);
    return 0;
}

void snakeMove(int dir) {
    //first clear the tail
    printf(&quot;\033[%d;%dH%c\n&quot;,snakeY[snakeLength-1]+1,snakeX[snakeLength-1]+1,BLANK_CELL);
    map[snakeY[snakeLength-1]][snakeX[snakeLength-1]]=BLANK_CELL;

    if(snakeX[0]+direx[dir]==foody&amp;&amp;snakeY[0]+direy[dir]==foodx) {//eat food
        eatFood=1;
        snakeLength++;//increase length
    }

    for(int i=snakeLength-1; i&gt;0; i--) {//body move
        snakeX[i]=snakeX[i-1];
        snakeY[i]=snakeY[i-1];
    }

    snakeX[0]+=direx[dir];//head move
    snakeY[0]+=direy[dir];
}

void show() {
    for(int i=0; i&lt;MAP_LENGTH; i++) {//output map
        for(int j=0; j&lt;MAP_LENGTH; j++) {
            printf(&quot;%c&quot;,map[i][j]);
        }
        printf(&quot;\n&quot;);
    }
}

void output(void) {
    printf(&quot;\033[%d;%dH%c\n&quot;,snakeY[0]+1,snakeX[0]+1,SNAKE_HEAD);//print snake
    printf(&quot;\033[%d;%dH%c\n&quot;,snakeY[1]+1,snakeX[1]+1,SNAKE_BODY);
    printf(&quot;\033[%d;%dH%c\n&quot;,snakeY[snakeLength-1]+1,snakeX[snakeLength-1]+1,SNAKE_BODY);
    //must empty buffers: printf+'\n' or fflush(stdout);

    map[snakeY[0]][snakeX[0]]=SNAKE_HEAD;
    map[snakeY[snakeLength-1]][snakeX[snakeLength-1]]=SNAKE_BODY;

    if(eatFood) {
        eatFood=0;
        if(putFood()) { //put food
            printf(&quot;\033[%d;%dH%c\n&quot;,foodx+1,foody+1,SNAKE_FOOD);
        }
    } else {
        printf(&quot;\033[%d;%dH%c\n&quot;,foodx+1,foody+1,SNAKE_FOOD);
    }
    printf(&quot;\033[13;1H\n&quot;);
}

int gameover(void) {
    if(snakeLength&gt;=(MAP_LENGTH-2)*(MAP_LENGTH-2))return 1;//the map is full

    if(map[snakeY[0]][snakeX[0]]==WALL_CELL)return 1;//not touch wall

    for(int j=1; j&lt;snakeLength; j++) {//doesn't eat itself
        if(snakeX[0]==snakeX[j]&amp;&amp;snakeY[0]==snakeY[j])return 1;
    }
    return 0;
}

int putFood(void) {
    int foodMap[MAP_LENGTH*MAP_LENGTH][2],len,ran;
    len=0;
    for(int i=1; i&lt;MAP_LENGTH-1; i++) {//put empty place into foodMap
        for(int j=1; j&lt;MAP_LENGTH-1; j++) {
            if(map[i][j]==BLANK_CELL) {
                foodMap[len][0]=i;
                foodMap[len][1]=j;
                len++;
            }
        }
    }

    if(len&gt;1)ran=rand()%len;//place food randomly
    else if(len==0)return 0;
    else ran=0;

    foodx=foodMap[ran][0];
    foody=foodMap[ran][1];
    return 1;
}

char whereGoNext() {
    char movable[4]= {'D','A','S','W'};
    int min=9999,minDir;
    for(int i=0; i&lt;4; i++) {
        snakeX[0]+=direx[i];
        snakeY[0]+=direy[i];

        if(!gameover()) {
            int cost=fabs(snakeX[0]-foody)+fabs(snakeY[0]-foodx);
            if(min&gt;cost) {
                min=cost;
                minDir=i;
            }
        }

        snakeX[0]-=direx[i];
        snakeY[0]-=direy[i];
    }
    if(min&lt;9999)
        return movable[minDir];
    else return 0;
}
</code></pre></article>
    </section>

    <footer class="ui attached segment dream-tags">
      
          <a class="ui label">No Tags</a>
      
      <div
        class="ui label"
        style="float: right; cursor: pointer;"
        onclick="savePostAsImg()">
        <i class="save icon"></i>Save as image
      </div>
    </footer>

    

    
    
    

  </div>
  <div class="sixteen wide mobile sixteen wide tablet four wide computer column">
    <article class="dream-header">
  <section class="ui top attached center aligned segment">
    <div class="ui small circular image">
      
        <img src="/img/sleep.jpg">
      
    </div>

    
    <h1 class="ui medium header">Lindixuan&#39;s blog<div class="sub header" style="margin-top: 0.5rem;">好耶！</div>
    </h1>
    

    <div class="ui horizontal list">
      
      <a class="item" href="/tags">
        <i class="tags icon" title="All Tags"></i>
      </a>
      <a class="item" href="/categories">
        <i class="th list icon" title="All Categories"></i>
      </a>
    </div>
  </section>

  

  

  <section class="ui attached segment header-socials">
    <nav class="ui secondary menu dream-menu dream-socials">
  
  
    <div class="item">
      <a href="mailto:1228210482@qq.com">
        <i class=" mail icon" title="Email"></i>
      </a>
    </div>
  

  

  

  

  

  

  

  
</nav>

  </section>

  <section class="ui bottom attached center aligned segment">
    
      <p>© 2020 - 2021 Hugo Theme Dream</p>
    

    <p>Powered by <a href="https://gohugo.io/" target="_blank">Hugo</a> with theme <a href="https://github.com/g1eny0ung/hugo-theme-dream" target="_blank">Dream</a>.</p>

    
  </section>
</article>

  </div>
</div>

          </div>
        </section>
        <section class="back">
          <div class="dream-max-width">
            <div class="ui centered relaxed grid dream-grid dream-back">
  
  
  

  <section class="sixteen wide mobile eight wide tablet four wide computer column dream-column">
    <article>
      <div class="ui top attached segment">
        <h3 class="ui header">Social Links</h3>
      </div>
      <div class="ui bottom attached segment">
        <nav class="ui secondary menu dream-menu dream-socials">
  
  
    <div class="item">
      <a href="mailto:1228210482@qq.com">
        <i class="large mail icon" title="Email"></i>
      </a>
    </div>
  

  

  

  

  

  

  

  
</nav>

      </div>
    </article>
  </section>

  <section class="sixteen wide mobile eight wide tablet four wide computer column dream-column">
    
  </section>

  
    
  
</div>

          </div>
        </section>
      </div>
    </div>

    <script>
  window.darkNav =  true 
</script>
<script src="/js/jquery.min.js"></script>
<script src="/js/semantic.min.js"></script>
<script src="/js/jquery.overlayScrollbars.min.js"></script>
<script src="/js/header.js"></script>
<script src="/js/main.js"></script>
<script src="/js/theme.js"></script>

    
<script src="/js/html2canvas.min.js"></script>
<script src="/js/post.js"></script>


  <script src="https://cdn.jsdelivr.net/gh/highlightjs/cdn-release/build/highlight.min.js"></script>

  
    
      <script src="https://cdn.jsdelivr.net/gh/highlightjs/cdn-release/build/languages/ocaml.min.js"></script>
     
  

  <script>
  hljs.initHighlightingOnLoad()
  setHighlightTheme()

  function setHighlightTheme() {
    var isDark = localStore.getItem('hugo-theme-dream-is-dark')
    var lightTheme = "gruvbox-light"
    var darkTheme = "gruvbox-dark"
    var theme = isDark ? darkTheme : lightTheme

    $('link[data-highlight]').attr('href', 'https://cdn.jsdelivr.net/gh/highlightjs/cdn-release/build/styles/' + theme + '.min.css')
    $('pre').css('background', isDark ? '#333' : '')
  }
</script>





    
      <div class="ui inverted segment" id="dream-search">
  <div class="ui search">
    <div class="ui transparent input">
      <input class="prompt" type="text" placeholder="Search" />
    </div>
    <div class="results"></div>
  </div>
</div>
<script>
  $(document).ready(function () {
    $.getJSON('https:\/\/lindixuan.gitee.io/index.json', function (data) {
      $('.ui.search').search({
        source: data,
        searchFields: ['title'],
        showNoResults: true,
      })
    })
  })
</script>
<script src="/js/search.js"></script>

    

    
  </body>
</html>
